import java.util.Stack;

public class Text {

    //实现函数 int sqrt(int x).
    //计算并返回 x 的平方根（向下取整）
    public int sqrt (int x) {
        if(x<=0){
            return 0;
        }
        int left = 1,right = x;
        while(true){
            int mid = (left + right)>>1;
            if(mid <= x / mid && (mid + 1) > x / (mid + 1)){
                return (int)mid;
            }else if(mid < x / mid){
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
    }

    // 判断一个字符串是否回文串
    // 方法一：
    public boolean judge (String str) {
        // 判断是否为回文串，正序和倒叙相同
        // 1) 先创立一个栈，就字符串按顺序放进去
        Stack<Character> stack = new Stack<>();
        for(int i=0;i<str.length();i++){
            char c = str.charAt(i);
            stack.push(c);
        }
        // 2) 再遍历一次字符串，将遍历的每一个字符与栈弹出的字符进行比较
        // 3） 只要有一个不相等就说明不是回文串，反之，则是 回文串
        for(int i = 0;i < str.length();i++){
            char c2 = str.charAt(i);
            if(c2!=stack.pop()){
                return false;
            }
        }
        return true;
    }
    // 方法二：
    public boolean judge2 (String str){
        for (int i = 0; i < str.length()/2; i++) {
            if(str.charAt(i)!=str.charAt(str.length()-1-i)){
                return false;
            }
        }
        return true;
    }
}
